package cn.pugle.oj.leetcode;


import cn.pugle.oj.catalog.LinkedProblem;

/**
 * https://leetcode.com/problems/add-two-numbers/
 *
 *
 * <p>You are given two linked lists representing two non-negative numbers.
 * The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
 * <p>
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * <p>
 * note 注意方法中的循环的处理， 即何时使用 break在中间跳出循环 见代码大全
 *
 * @author tzp
 * @date 15-10-10
 */
public class LC2_AddTwoNumbers implements LinkedProblem {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = l1;
        int jin = 0;
        while (true) {
            l1.val += l2.val + jin;
            jin = l1.val / 10;
            l1.val %= 10;
            if (l1.next == null && l2.next == null && jin == 0) {
                break;
            }
            l1 = nonNullNext(l1);
            l2 = nonNullNext(l2);
        }
        return root;
    }

    private final ListNode nonNullNext(ListNode l) {
        if (l.next == null) {
            l.next = new ListNode(0);
        }
        return l.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(9);
        l1.next.next.next = new ListNode(2);
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(7);
        ListNode listNode = new LC2_AddTwoNumbers().addTwoNumbers(l1, l2);
        do {
            System.out.println(listNode.val + " ");
            listNode = listNode.next;
        } while (listNode != null);
    }
}
